from random import choice


"""
380. O(1) 时间插入、删除和获取随机元素
https://leetcode.cn/problems/insert-delete-getrandom-o1/description/?envType=study-plan-v2&envId=top-interview-150
"""
class RandomizedSet:
    def __init__(self):
        # 变长数组可以在 O(1) 的时间内完成获取随机元素操作，但是由于无法在 O(1) 的时间内判断元素是否存在，因此不能在 O(1) 的时间内完成插入和删除操作。
        self.nums = []
        # 哈希表可以在 O(1) 的时间内完成插入和删除操作，但是由于无法根据下标定位到特定元素，因此不能在 O(1) 的时间内完成获取随机元素操作。
        self.indices = {}

    def insert(self, val: int) -> bool:
        if val in self.indices:
            return False
        self.indices[val] = len(self.nums)
        self.nums.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.indices:
            return False
        # 找到 val 的索引
        id = self.indices[val]
        # 替换值：将self.nums列表中最后一个元素的值赋给索引为id的位置，实现值的替换而不是直接删除，以保持列表的连续性。
        self.nums[id] = self.nums[-1]
        # 更新索引映射：由于值已被替换，需要更新self.indices中相应元素的索引位置，使其指向新的位置（即原来val的位置）
        self.indices[self.nums[id]] = id
        # 移除最后一个元素：从self.nums中移除最后一个元素（此时该元素的值已经被移到了前面）。
        self.nums.pop()
        # 删除索引项：从self.indices中删除val对应的索引项，因为它已经从列表中移除了
        del self.indices[val]
        return True

    def getRandom(self) -> int:
        return choice(self.nums)

if __name__ == '__main__':
    obj = RandomizedSet()
    print(obj.insert(1))
    print(obj.insert(4))
    print(obj.insert(6))
    print(obj.remove(4))
    print(obj.remove(2))
    print(obj.insert(2))
    print(obj.getRandom())
